//
//  SqListExt.cpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/6/22.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#include "SqListExt.hpp"

// 测试功能，获取表长
int getListLenth(SqList L)
{
    return L.length;
}

// 删除最小值，然后用最后一个元素填补
bool deleteMinimum(SqList &L, int &e)
{
    if (L.length == 0)
        return false;
    int min = 0; // 最小值指针
    for (int i = 1; i < L.length; i++) {
        if (L.data[i] < L.data[min])
            min = i;
    }
    e = L.data[min];
    L.data[min] = L.data[L.length - 1];
    L.length--;
    return true;
}

// 高效逆序，要求空间复杂度为O(1)
bool listReverse(SqList &L)
{
    if (L.length == 0)
        return false; // 判断空表
    
    int i = 0, j = L.length - 1;
    int temp;
    
    while (i < j) {
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
        i++;
        j--;
    }
    
    return true; // 时间复杂度O(n),空间复杂度O(1)
}

// ✨时间复杂度O(n)空间复杂度O(1)删除所有值为x的元素
bool removeX(SqList &L, int x)
{
    if (L.length == 0) {
        return false;
    }

    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] != x) {
            L.data[k++] = L.data[i];
        }
    }
    L.length = k;
    return true;
}

// ✨有序顺序表删除s和t之间的所有值
bool delRange(SqList &L, int s, int t)
{
    if (L.length == 0) { // 判断表
        return false;
    }
    if (s >= t) { // 判断数据合法性
        return false;
    }
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < s || L.data[i] > t) {
            L.data[k++] = L.data[i];
        }
    }
    L.length = k;
    return true;
}

// 顺序表删除s和t之间的所有值
bool delRangeNormal(SqList &L, int s, int t)
{
    if (L.length == 0) { // 判断表
        return false;
    }
    if (s >= t) { // 判断数据合法性
        return false;
    }
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] < s || L.data[i] > t) {
            L.data[k++] = L.data[i];
        }
    }
    L.length = k;
    return true;
}

// ✨删除有序顺序表中重复的元素
bool delRepeat(SqList &L)
{
    if (L.length == 0) { // 判断表是否为空
        return false;
    }
    int k = 0; // 指针
    for (int i = 1; i < L.length; i++) {
        if (L.data[k] != L.data[i]) {
            L.data[++k] = L.data[i];
        }
    }
    L.length = k + 1;
    return true; // 时间复杂度O(n)
}

// 两个有序顺序表合并为一个并返回
bool mergeList(SqList L1, SqList L2, SqList &L)
{
    if (L1.length + L2.length > MAX_SIZE) { // 判断是否会溢出
        return false;
    }
    int p1 = 0, p2 = 0, p = 0; // 遍历指针
    while (p1 < L1.length && p2 < L2.length) {
        if (L1.data[p1] < L2.data[p2]) {
            L.data[p++] = L1.data[p1++];
        } else {
            L.data[p++] = L2.data[p2++];
        }
    }
    while (p1 < L1.length) {
        L.data[p++] = L1.data[p1++];
    }
    while (p2 < L2.length) {
        L.data[p++] = L2.data[p2++];
    }
    L.length = p;
    return true;
}

// A[m+n]中存在2个线性表(a1,a2...am)(b1,b2...bn)
// 转换为(b1,b2...bn)(a1,a2...am)
void arrayReverse(int *A, int p, int q)
{
    int temp;
    while (p < q) {
        temp = A[p];
        A[p] = A[q];
        A[q] = temp;
        p++;
        q--;
    }
}
void innerArrayReverse(int *A, int m, int n)
{
    // 原地逆转
    int p = 0;
    int q = m + n - 1;
    arrayReverse(A, p, q);
    // 前n个元素逆转
    p = 0;
    q = n - 1;
    arrayReverse(A, p, q);
    // 后m个元素逆转
    p = n;
    q = m + n - 1;
    arrayReverse(A, p, q);
}

// a1,a2...an递增有序，快速找到最小元素x。
// 若找到则与后继元素交换，找不到则插入使其任然有序
void fundx(int *A, int len ,int x)
{
    // 二分法查找x,O(log2n)
    int low = 0;
    int high = len - 1;
    int mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;
        if (A[mid] == x) {
            break;
        } else if (A[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    // 如果找到了x，与后继元素交换
    if (A[mid] == x && mid < len - 1) {
        int temp = A[mid];
        A[mid] = A[mid + 1];
        A[mid + 1] = temp;
    } else {
        // 插入x使有序
        /** 二分法x的位置
        mid > x: ... [h] x [mid,l];
        mid < x: [mid,h] x [l]
        */
        int i = len - 1;
        for (; i > high; i--) {
            A[i + 1] = A[i];
        }
        A[high+1] = x;
    }
}

// (X0,X1...Xn-1) -> (Xp,Xp+1...Xn-1,X0,X1...Xp-1)
void moveArray(int *arr, int n, int p)
{
    // 原地逆序，然后将前n-p个元素逆序，再将后p个元素逆序
    // 事件复杂度O(n),空间复杂度O(1).
    int low = 0;
    int high = n - 1;
    arrayReverse(arr, low, high);
    arrayReverse(arr, 0, n-p-1);
    arrayReverse(arr, n-p, n-1);
}

// ✨中位数：中间的数
// 等长n,升序的A和B，找出它们的中位数。
int searchMidNumber(int *A, int *B, int n)
{
    
    // A和B比较n次即可获得中位数。
    // 事件复杂度O(n)空间复杂度O(1)
    int k = 0; // 记录比较次数
    int mid = 0; // 保存中位数
    int pa = 0; // a指针
    int pb = 0; // b指针

    while (k < n) {
        if (A[pa] <= B[pb]) {
            mid = A[pa++];
        } else {
            mid = B[pb++];
        }
        k++;
    }

    return mid;
}

// ✨主元素：m个相同的值，m > n / 2
// 找到数组中的主元素并返回，否则返回-1
int searchMainElement(int *arr, int n)
{
    // 循环数组，如果与当前主元素值相同则计数器+1，否则-1.当计数器为-1时，更换新的主元素值并将counter设为1.
    // 最后循环累加，如果个数超过n/2，则为主元素。
    // 事件复杂度O(n)空间复杂度O(1)
    int p = 0; // 指针
    int counter = 1; // 计数器
    int main = arr[p];
    
    for (int i = 1; i < n; i++) {
        if (arr[p] == arr[i]) {
            counter++;
        } else {
            counter--;
            if (counter < 0) {
                counter = 1;
                main = arr[i];
            }
        }
    }
    int num = 0;
    for (int j = 0; j < n; j++) {
        if (arr[j] == main) {
            num++;
        }
    }
    if (num > n / 2) {
        return main;
    }
    
    return -1;
}

// ✨给定一个n个整数的数组，找出未出现的最小正整数
int searchMinNumber(int *arr, int n)
{
    // 设置一个长度为n的数组a，遍历arr，若1<=arr[i]<=n
    // 则a[arr[i]] = 1。最后根据a的值来判断最小正整数。
    // 事件复杂度O(n) 空间S(n)
    // 将数组都设为0
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = 0;
    }
    // 出现的整数设为1
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0 && arr[i] <= n) {
            a[arr[i] - 1] = 1;
        }
    }
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            return i + 1;
        }
    }
    return n + 1;
}
